package com.cqs.leetcode;

import com.cqs.leetcode.ds.ArraysUtils;

import java.util.Stack;


/**
 * Created by cqs on 2018/3/30.
 */
public class NextGreaterElementII {


    public int[] nextGreaterElements(int[] nums) {
        if (nums == null || nums.length == 0) return nums;
        Stack<Integer> stack = new Stack<>();
        int[] result = new int[nums.length];
        //循环退出有待优化
        for (int i = 0; i < (nums.length << 2); i++) {
            int idx = i % nums.length;
            while (stack.size() > 0 && nums[stack.peek()] < nums[idx]) {
                result[stack.pop()] = nums[idx];
            }
            if (i < nums.length) {
                result[i] = -1;
                stack.push(idx);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        NextGreaterElementII g = new NextGreaterElementII();
        int[] arr = {5, 4, 3, 2, 1};
//        arr = ArraysUtils.randInts(10);
        ArraysUtils.print(arr);
        int[] ints = g.nextGreaterElements(arr);
        ArraysUtils.print(ints);

    }
}
